package com.peng.leetcode.list;

/**
 * IsPalindrome
 * 验证是否是回文字符串
 *
 * @author: lupeng6
 * @create: 2020/12/21 20:59
 */
public class IsPalindrome {

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(2, new ListNode(1)))));
        System.out.println(new Solution().isPalindrome(listNode));
    }


    static class Solution {
        public boolean isPalindrome(ListNode head) {
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode slow = dummy;
            ListNode fast = dummy;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode reverseHeader = reverse(slow.next);
            while (reverseHeader != null) {
                if (reverseHeader.val != head.val) {
                    return false;
                }
                reverseHeader = reverseHeader.next;
                head = head.next;
            }
            return true;
        }

        public ListNode reverse(ListNode curr) {
            ListNode newHeader = null;
            while (curr != null) {
                ListNode next = curr.next;
                curr.next = newHeader;
                newHeader = curr;
                curr = next;
            }
            return newHeader;
        }
    }

}
